<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="description" content="">
    <meta name="that js dude" content="">    
    <title>JS: interview Questions -5</title>

    <link rel="shortcut icon" href="images/favicon.jpg">    
    <link rel="stylesheet" href="css/bootstrap.min.css" >
    <link rel="stylesheet" href="css/zenburn.css">
    <!-- Custom styles for this template -->
    <style>
      /* Move down content because we have a fixed navbar that is 50px tall */
      body {        
        padding-bottom: 20px;
      }
      .purpleBold{
        color:purple;        
        font-weight: bold;
      }
      .gray{
        color: gray;
      }
      .blueish{
        color: rgba(151, 182, 209, 0.98);
      }
      .singInStuff{
        margin-top: 9px;
      }
      #uName{
        margin-top: -7px;
      }
      .skipListItem{
        list-style-type: none;
      }
      .skipListItem a{
        color: inherit;
      }
      a:visited
      { 
        color: rgba(218, 209, 149, 0.98);
      }
      .padding10Px{
        padding: 10px;
      }
      /*style for demo*/
      
    </style>

    <!-- Just for debugging purposes. Don't actually copy this line! -->
    <!--[if lt IE 9]><script src="docs-assets/js/ie8-responsive-file-warning.js"></script><![endif]-->

    <!-- HTML5 shim and Respond.js IE8 support of HTML5 elements and media queries -->
    <!--[if lt IE 9]>
      <script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
      <script src="https://oss.maxcdn.com/libs/respond.js/1.3.0/respond.min.js"></script>
    <![endif]-->
  </head>
 
  <body>

    <!-- Main jumbotron for a primary marketing message or call to action -->
    <div class="jumbotron">
      <div class="container">
        <h1>JS: Interview Questions</h1>        
        <h4>Search and sort related interview questions for intermediate JavaScript developers</h4>
        <h2>part-5: intermediate</h2>
        <p>June 29, 2014</p>
<!--         <div id="fb-root"></div><div class="fb-like" data-href="http://www.thatjsdude.com/interview/dom.html" data-layout="button_count" data-action="like" data-show-faces="false" data-share="false"></div><div class="g-plusone"></div> 
 -->      </div> 
    </div>
    <div class="container container-fluid">
      <!-- Example row of columns -->

      <div class="row center">        
        <!-- <iframe width="853" height="480" src="//www.youtube.com/embed/Rx_JFOSxgpY" frameborder="0" allowfullscreen></iframe> -->
      </div>
           
      <!-- <p class="gray">if you are little more comfortable or claim to be comfortable with javascript, these questions would not be enough for you. more coming</p>
      <p class="gray"> <span class="purpleBold">More Questions</span> <a href="css.html">css interview questions</a>, <a href="html.html">html interview questions</a> </p> -->
    <div id="questionList">
      <h2>todo list</h2>
      <ol>
        <li>add questions</li>
        <li></li>
        <li></li>
        <li></li>
        <li></li>
      </ol>
    </div>
    
      <div id="binarySearch">
        <h2>binary search</h2>
        <p><strong>Question:</strong> How to implement binary search algorithm?</p>
        <p><strong>Answer:</strong>Binary search tries to find an item in a sorted list. For example, if you have an array like <code>[3,9,11,21,32,37,43,56,63,69,78]</code> and you are looking for 69.</p>
        <p><strong>How it works:</strong>Lets select the middle one, you got: 37. You are looking for 69. As you know, the array is sorted, you will know that 69 will be after 37. This means upper half of the array. Now, you will go and check the middle item of the upper half of the array. In that way, you are saving time to search the item in the lower half of the array.</p>
        <p>The middle item of the upper half of the array is 63. Which is smaller than the number you are looking for. Hence, you can skip the lower part of the upper half. This means, your item will be in the top most quarter of the array. Now, you will keep the right side and pick the middle</p>
        <p>The middle of the right side is 69. Thats what you were looking for.</p>
        <p><strong>Why binary search</strong> If you were using linear search (start from the left and check one by one), you have to check 10 times to find the item. If you use binary search, you get after three times. You see the benefits!!</p>
        <img src="images/binarySearch.png" alt="">
        <p>Now if you have a million items in an array. For example, you have number 0 to 1000,000 and you want to find out 696,969. The binary search will take only 17 steps to find the item. where as if you start a linear search, it will take 696,969 steps to find the item.</p>
        <pre><code>
function binarySearchIterative(arr, val){
   var start = 0,
       end = arr.length-1, 
       mid, 
       midVal;
    
   while(end >= start){
     mid = Math.floor((start+end)/2);

     midVal = arr[mid];
          
     if(midVal==val)
         return mid;
     
     if(val&lt;midVal)
         end = mid - 1;
     if(val&gt;midVal)
         start = mid + 1;
          
  } 
  return -1;
}

//try it now
binarySearchIterative([1,2,3,4,5], 1); //0
binarySearchIterative([1,2,3,4,5], 5); //4
binarySearchIterative([1,2,3,4,5], 55); //-1
        </code></pre>
        <p><strong>Complexity</strong></p>
        <pstrong  Performance</p>
        <p>Recusrive algo</p>
        <pre><code>
function binarySearchRecursive(arr, val, startIdx, endIdx){
   var mid = Math.floor((startIdx + endIdx)/2), 
       midVal = arr[mid];
   
   if(midVal == val)
      return mid;
   if (endIdx &lt; startIdx)
      return -1;

   if (val&lt;midVal)
      return binarySearchRecursive(arr, val, startIdx, mid -1);
   else if (val &gt; midVal)
      return binarySearchRecursive(arr, val, mid + 1, endIdx);

}

//try it now
binarySearchRecursive([1,2,3,4,5], 1, 0, 4); //0
binarySearchRecursive([1,2,3,4,5], 5, 0, 4); //4
binarySearchRecursive([1,2,3,4,5], 2, 0, 4); //1
binarySearchRecursive([1,2,3,4,5], 22, 0, 4); //-1
        </code></pre>
        <p>ref: <a href="http://en.wikipedia.org/wiki/Binary_search_algorithm">binary search</a></p>
      </div>  
      
    <div>
      <h3 class="purpleBold">Express anger!</h3>        
      <!-- <p class="gray">Feel free to express your anger (sorry folks, you have to use g+.). Also point out my mistakes ( technical, wrong answer, spelling, grammar, sentence..., whatever), let your dude learn and grow.</p>
      <script src="https://apis.google.com/js/plusone.js"></script>
      <div class="g-comments"
          data-href="http://www.thatjsdude.com/interview/dom.html"
          data-width="642"
          data-first_party_property="BLOGGER"
          data-view_type="FILTERED_POSTMOD">
      </div>         -->
    </div>
      <hr>

      <footer>
        <p>&copy;thatJSDude 2014</p>
      </footer>
    </div> <!-- /container -->


    <!-- Bootstrap core JavaScript
    ================================================== -->
    <!-- Placed at the end of the document so the pages load faster -->
    <script src="js/jquery-2.0.3.min.js"></script>    
    <script src="js/bootstrap.min.js"></script>
    <script src="js/highlight.pack.js"></script>    
    <script>hljs.initHighlightingOnLoad();</script>
    <script src="js/toggleExample.js"></script>
    <script type="text/javascript">
      // //social plugins
      // //g+
      // (function() {
      //   var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true;
      //   po.src = 'https://apis.google.com/js/platform.js';
      //   var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s);
      // })();
      // //fb
      // (function(d, s, id) {
      //   var js, fjs = d.getElementsByTagName(s)[0];
      //   if (d.getElementById(id)) return;
      //   js = d.createElement(s); js.id = id;
      //   js.src = "//connect.facebook.net/en_US/all.js#xfbml=1";
      //   fjs.parentNode.insertBefore(js, fjs);
      // }(document, 'script', 'facebook-jssdk'));
    </script>
    <script type="text/javascript">        
        document.getElementById('listToDestroy').addEventListener('click', function (e) {
          var elm = e.target.parentNode;
          elm.parentNode.removeChild(elm);
          e.preventDefault();
        }); 

        document.getElementById('doubleHolder').addEventListener('click', function (e) {
   
           if(e.target.classList.contains('double')){
              var btn = document.createElement('button');
              btn.setAttribute('class', 'double');
              btn.innerHTML = 'double';

              var btn2 = document.createElement('button');
              btn2.setAttribute('class', 'double');
              btn2.innerHTML = 'double';
             
              this.appendChild(btn);
              this.appendChild(btn2);
              this.removeChild(e.target);   
           }
        }); 
    </script>
  </body>
</html>
